public class Solution576 {
    private static final int mod = 1000000007;
    int[] dx=new int[]{1,0,-1,0};
    int[] dy=new int[]{0,1,0,-1};

    public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        if (maxMove==0){
            return 0;
        }
        int[][][] f=new int[m][n][maxMove];
        f[startRow][startColumn][0]=1;
        for (int i=1;i<maxMove;i++){
            for (int j=0;j<m;j++){
                for (int k=0;k<n;k++){
                    for (int l=0;l<4;l++){
                        if (valid(j+dx[l],k+dy[l],m,n)){
                            f[j][k][i]=(f[j][k][i]+f[j+dx[l]][k+dy[l]][i-1]) %mod;
                        }
                    }
                }
            }
        }
        int ans=0;
        if (m!=1 && n!=1) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < maxMove; j++) {
                    ans = (ans + f[0][i][j]) %mod;
                    ans = (ans + f[m - 1][i][j]) %mod;
                }
            }
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < maxMove; j++) {
                    ans = (ans + f[i][0][j]) %mod;
                    ans = (ans + f[i][n - 1][j])%mod;
                }
            }
            return ans;
        }
        if (m!=1 && n==1){
            for (int i=0;i<m;i++) {
                for (int j = 0; j < maxMove; j++) {
                    ans = (ans + f[i][0][j] * 2 % mod)%mod;
                }
            }
            for (int j = 0; j < maxMove; j++) {
                ans = ((ans + f[0][0][j])%mod + f[m - 1][0][j]) % mod;
            }
            return ans;
        }
        if (m==1 && n!=1) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < maxMove; j++) {
                    ans = (ans + f[0][i][j] * 2 %mod )%mod;
                }
            }
            for (int j = 0; j < maxMove; j++) {
                ans = ((ans + f[0][0][j])%mod + f[0][n - 1][j])%mod;
            }
            return ans;
        }
        return 4;
    }
    public boolean valid(int a,int b,int m,int n){
        return a>=0 && a<m && b>=0 && b<n;
    }

    public static void main(String[] args) {
        System.out.println(new Solution576().findPaths(1,3,3,0,1));
    }
}
